#include "AB.h"

template <typename T>
AB<T>::AB()
{
    Raiz=NULL;
}
template <typename T>
bool AB<T>::Vacio()
{
    return Raiz==NULL;
}
template <typename T>
bool AB<T>::Vacio(Pagina<T>* raiz)
{
    return raiz==NULL;
}
template <typename T>
void AB<T>::Insertar(int clave, T Datos)
{
    if(Vacio())
    {
        Raiz=new Pagina<T>();
        Raiz->setClave(clave,0);
        Raiz->setCuentas(1);
        Raiz->setDato(Datos,0);
    }
    else
        Insertar(clave, Datos, &Raiz);
    VIFS::V_WriteLog("B: insercion");
}
template <typename T>
void AB<T>::Insertar(int clave, T Datos, Pagina<T>** raiz)
{
    bool EAnp=false;
    bool* EA=&EAnp;
    int XInp=0;
    int* XI=&XInp;
    T XTnp;
    T* XT=&XTnp;
    Pagina<T>* Xrnp=NULL;
    Pagina<T>**Xr=&Xrnp;
    Pagina<T>* P=NULL;


    Empujar(clave,Datos,*raiz,EA,XI,XT,Xr);
    if (*EA) {
        P=new Pagina<T>();
        P->setCuentas(1);
        P->setClave(*XI,0);
        P->setDato(*XT,0);
        P->setPagina(*raiz,0);
        P->setPagina(*Xr,1);
        *raiz=P;
    }
}
template <typename T>
void AB<T>::Empujar(int clave, T Datos, Pagina<T> *raiz, bool *EA, int *MdnaI, T *MdnaT, Pagina<T> **Xr)
{
    int knp=0;
    int* k=&knp;
    bool estanp=false;
    bool* esta=&estanp;
    //*esta=false;

    if (Vacio(raiz)) {
        *EA=true;
        *MdnaI=clave;
        *MdnaT=Datos;
        Xr=NULL;

    } else {
        BuscarNodo(clave, Datos,raiz,esta,k);
        if (*esta) {
            std::cout<<"repetido"<<std::endl;
            //return;
        } else {
            Empujar(clave,Datos,raiz->getPagina(*k),EA,MdnaI,MdnaT,Xr);
            if (*EA) {
                if (!raiz->Llena()) {
                    *EA=false;
                    MeterHoja(*MdnaI,*MdnaT,*Xr,raiz,k);
                } else {
                    *EA=true;
                    *Xr=DividirNodo(*MdnaI, *MdnaT,*Xr,raiz,k, MdnaI, MdnaT);
                }
            }
        }
    }
}
template <typename T>
void AB<T>::BuscarNodo(int clave, T Datos, Pagina<T> *pag, bool *Encontrado, int *pos)
{
    if (clave<pag->getClave(0)) {
        *Encontrado=false;
        *pos=0;
    } else {
        *pos=(pag->getCuentas());
        while (clave<pag->getClave(*pos-1) && *pos>0) {
            *pos=(*pos-1);
        }
        *Encontrado=clave==pag->getClave(*pos-1);
    }
}
template <typename T>
void AB<T>::MeterHoja(int clave, T Datos, Pagina<T> *Xder, Pagina<T> *P, int *k)
{
    for (int i = P->getCuentas();
         i > *k;
         i--) {
        P->setClave(P->getClave(i-1),i);
        P->setDato(P->getDato(i-1),i);
        P->setPagina(P->getPagina(i-1),i);
    }
    P->setClave(clave,(*k));
    P->setDato(Datos,(*k));
    P->setPagina(Xder,(*k+1));
    P->setCuentas(P->getCuentas()+1);
}
template <typename T>
Pagina<T> * AB<T>::DividirNodo(int clave, T Datos, Pagina<T> *Xder, Pagina<T> *P, int *k, int *MdnaI, T *MdnaT)
{

    int posmda;
    if (*k<=2) {
        posmda=2;
    } else {
        posmda=3;
    }
    Pagina<T>* Mder=new Pagina<T>();
    for(int i=posmda; i<4;i++)
    {
        Mder->setClave(P->getClave(i),i-posmda);
        Mder->setDato(P->getDato(i), i-posmda);
        Mder->setPagina(P->getPagina(i+1), i-posmda+1);
    }
    //--------Mder->setPagina(P->getPagina(i+1), i-posmda+1);
    Mder->setCuentas(4-posmda);
    P->setCuentas(posmda);
    if (*k<=2) {
        MeterHoja(clave,Datos,Xder,P,k);
    } else {
        int temp1=*k-posmda;
        MeterHoja(clave, Datos, Xder,Mder,&temp1);
    }
    *MdnaI=P->getClave(P->getCuentas()-1);
    *MdnaT=P->getDato(P->getCuentas()-1);
    Mder->setPagina(P->getPagina(P->getCuentas()),0);
    P->setCuentas(P->getCuentas()-1);
    VIFS::V_WriteLog("B: dividir");
    return Mder;
}
template <typename T>
QString AB<T>::Inorden()
{
    return Inorden(Raiz);
}
template <typename T>
QString AB<T>::Inorden(Pagina<T>* raiz)
{
    QString ret="";
    if (!Vacio(raiz))
    {
        ret+=Inorden(raiz->getPagina(0));
        for (int i=0; i<raiz->getCuentas();i++)
        {
            ret+=QString::number(raiz->getClave(i))+" ";
            ret+=Inorden(raiz->getPagina(i+1));
        }
    }
    return ret;
}
template <typename T>
bool AB<T>::Valido(int clave)
{
    return Valido(clave,Raiz);
}
template <typename T>
bool AB<T>::Valido(int clave, Pagina<T> *raiz)
{
    if (Vacio(raiz))
    {
        return false;
    }
    else
    {
        if (clave<raiz->getClave(0))
            return Valido(clave,raiz->getPagina(0));
        else
        {
            int i=raiz->getCuentas()-1;
            while(i>0&&clave<raiz->getClave(i))
            {
                i--;
            }
            if(raiz->getClave(i)==clave)
                return true;
            else
            {
                return Valido(clave,raiz->getPagina(i));
            }
        }
    }
}
template <typename T>
T AB<T>::Index(int clave)
{
    return Index(clave,Raiz);
}
template <typename T>
T AB<T>::Index(int clave, Pagina<T> *raiz)
{
    if (clave<raiz->getClave(0))
        return Index(clave,raiz->getPagina(0));
    else
    {
        int i=raiz->getCuentas()-1;
        while(i>0&&clave<raiz->getClave(i))
        {
            i--;
        }
        if(raiz->getClave(i)==clave)
            return raiz->getDato(i);
        else
        {
            return Index(clave,raiz->getPagina(i+1));
        }
    }
}

//borrado

//

template <typename T>
Pagina<T>* AB<T>::getRaiz()
{
    return Raiz;
}

template class AB<hola>;
template class AB<B>;




















